#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

typedef struct __avl_node {
    struct __avl_node *left;
    struct __avl_node *right;
    int key;
    int factor;
} avl_node;

/***************************************
   a      a        b
    \  =>  \  =>  / \
     b      b    a   c
             \
	          c
**************************************/
avl_node *avl_rotate_rr(avl_node *node)
{
    avl_node *tmp = node->right;
    node->right = NULL;
    tmp->left = node;

    node->factor = tmp->factor = 0;
    return tmp;
}

/*****************************************
a	  a       b
 \	=> \ =>  /\
  c     c   a  c
       /
      b
*****************************************/
avl_node *avl_rotate_rl(avl_node *node)
{
    avl_node *tmp = node->right->left;
    node->right = NULL;
    tmp->left = node;
	tmp->right = node->right;

    node->factor = tmp->factor = 0;
    return tmp;
}

/***************************************
   a      a      b
  /  =>  /  =>  /\
 b      b      c  a
       /
	  c
**************************************/
avl_node *avl_rotate_ll(avl_node *node)
{
    avl_node *tmp = node->left;
    node->left = NULL;
    tmp->right = node;

    node->factor = tmp->factor = 0;
    return tmp;
}

/***************************************
   a      a      c
  /  =>  /  =>  /\
 b      b      b  a
         \
	      c
**************************************/
avl_node *avl_rotate_lr(avl_node *node)
{
    avl_node *tmp = node->left;
    node->left = NULL;
    tmp->right = node;

    node->factor = tmp->factor = 0;
    return tmp;
}

avl_node *avl_insert(avl_node **pnode,
                    int key) 
{
    /*the avl tree is empty*/
    if (*pnode == NULL) {
        *pnode = calloc(1, sizeof(avl_node));
        (*pnode)->key = key;
        return *pnode;
    }
    
    if (key < (*pnode)->key) {  //insert into left tree
        (*pnode)->left = avl_insert(&(*pnode)->left, key);
        if ( ++(*pnode)->factor == 2 ) {
            
            if (key < (*pnode)->left->key) {
                *pnode = avl_rotate_ll(*pnode);
            } else if (key > (*pnode)->left->key) {
                *pnode = avl_rotate_lr(*pnode);
            }
            
        }

    } else if (key > (*pnode)->key) {   //insert into right tree
        (*pnode)->right = avl_insert(&(*pnode)->right, key);
        if ( --(*pnode)->factor == -2) {
            
            if (key > (*pnode)->right->key) {
                *pnode = avl_rotate_rr(*pnode);
            } else if (key < (*pnode)->left->key) {
                *pnode = avl_rotate_rl(*pnode);
            }
        }
    }
    
    return *pnode;
}

void avl_tree_trval(avl_node *node)
{
    if (!node)
        return;
    static int n;

    avl_tree_trval(node->left);
    printf("[%d] data = %d\n", ++n, node->key);
    avl_tree_trval(node->right);
}

int main(int argc, char **argv)
{
    int i;
    avl_node *root = NULL;
    int key[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    for (i = 0; i < atoi(argv[1]); i++) {
        avl_insert(&root, key[i]);
    }
    
    avl_tree_trval(root);
    return 0;
}
